﻿//class Solution {
//public:
//    void quick_sort(vector<int>& arr, int l, int r, int k)
//    {
//        if (l >= r) return;
//        int mid = partSort(arr, l, r);
//        if (mid == k) return;   //mid 等于K返回
//        else if (mid < k)
//            quick_sort(arr, mid + 1, r, k); //mid < k 处理右子数组
//        else
//            quick_sort(arr, l, mid - 1, k); //处理左子数组
//    }
//    int partSort(vector<int>& arr, int l, int r)
//    {
//        int keyi = arr[l];
//        int i = l, j = r;
//        while (i < j)
//        {
//            while (i < j && arr[j] >= keyi) j--;//右边先找比keyi小的
//            while (i < j && arr[i] <= keyi) i++;//左边找比keyi大的
//            swap(arr[i], arr[j]);//找到交换，大的就换到右边，小的换到左边
//        }
//        swap(arr[l], arr[i]);//最后交换keyi
//        return i;//返回keyi的位置
//    }
//    vector<int> getLeastNumbers(vector<int>& arr, int k) {
//        vector<int> res;
//        if (k == 0) return res;
//        quick_sort(arr, 0, arr.size() - 1, k);
//        for (int i = 0; i < k; ++i) res.push_back(arr[i]);//将前K个数返回
//        return res;
//    }


    // vector<int> res(k,0);
    // sort(arr.begin(),arr.end());
    //     for(int i = 0;i < k;++i){
    //         res[i] = arr[i];
    //     }
    //     return res;


    // vector<int> res;
    // priority_queue<int> pq;
    // if(k == 0) return res;
    // for(int i = 0; i < arr.size();++i)
    // {
    //     if(pq.size() < k){ //堆的元素个数小于K就插入堆
    //         pq.push(arr[i]);
    //     }
    //     else if(pq.top() > arr[i]){ //比堆顶元素小的插入堆
    //         pq.pop();
    //         pq.push(arr[i]);
    //     }
    // }
    // while(!pq.empty()){ //将队里的元素插入res返回
    //     res.push_back(pq.top());
    //     pq.pop();
    // }
    // return res;

//};


//class MedianFinder {
//public:
//    priority_queue<int> max_heap;//大堆
//    priority_queue<int, vector<int>, greater<int>> min_heap;//小堆
///** initialize your data structure here. */
//    MedianFinder() {
//
//    }
//
//    void addNum(int num) {
//
//
//        if (max_heap.size() == min_heap.size()) {
//            min_heap.push(num);
//            max_heap.push(min_heap.top());
//            min_heap.pop();
//        }
//        else {
//            max_heap.push(num);
//            min_heap.push(max_heap.top());
//            max_heap.pop();
//        }
//
//    }
//    double findMedian() {
//        if (max_heap.size() != min_heap.size()) return max_heap.top();
//        return (max_heap.top() + min_heap.top()) / 2.0;
//    }
//};

class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        // priority_queue<int> pq;
        // vector<int> ans;
        // if(arr.empty() || k < 1) return ans;
        // for(int i = 0; i < arr.size();++i)
        // {
        //     if(pq.size() < k)
        //     {
        //         pq.push(arr[i]);
        //     } 
        //     else if(pq.top() > arr[i])
        //     {

        //          pq.pop();
        //           pq.push(arr[i]);
        //     }
        // }
        // while(!pq.empty())
        // {
        //     ans.push_back(pq.top());
        //     pq.pop();
        // } 
        // reverse(ans.begin(),ans.end());
        // return ans;
    }
};